/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-common-substring
   @Language: C++
   @Datetime: 16-02-09 05:57
   */

// Method 1, DP, Time O(n^2), Space O(n^2), Time 7ms
class Solution {
public:
	/**
	 * @param A: A string
	 * @param B: A string
	 * @return: the length of the longest common substring.
	 */
	int longestCommonSubstring(string &A, string &B) {
		// write your code here
		int la=A.length(), lb=B.length(), max=0;
		vector<vector<int> > dp(la+1,vector<int>(lb+1,0));
		for(int i=1; i<=la; ++i){
			for(int j=1; j<=lb; ++j){
				if (A[i-1]!=B[j-1]) dp[i][j]=0;
				else dp[i][j]=dp[i-1][j-1]+1;
				max=max>dp[i][j]?max:dp[i][j];
			}
		}
		return max;
	}
};

// Method 2, DP with Compact State, Time O(n^2), Space O(n)
class Solution {
public:
	/**
	 * @param A: A string
	 * @param B: A string
	 * @return: the length of the longest common substring.
	 */
	int longestCommonSubstring(string &A, string &B) {
		// write your code here
		int la=A.length(), lb=B.length(), max=0;
		vector<int> dp(lb+1,0);
		for(int i=1; i<=la; ++i){
			for(int j=lb; j; --j){
				if(A[i-1]!=B[j-1]) dp[j]=0;
				else dp[j]=dp[j-1]+1;
				max=max>dp[j]?max:dp[j];
			}
		}
		return max;
	}
};
